package com.gxc.recursion;

/**
 * 一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右 四个位置相连，
 * 如果有一片1连在一起，这个部分叫做一个岛，
 * 求一个矩阵中有多少个岛?
 * [举例]
 * 001010
 * 111010
 * 100100
 * 000000
 * 这个矩阵中有三个岛
 */
public class IslandNum {

    public static void main(String[] args) {
        int[][] arr = createArray();
        System.out.println(arr.length);
        System.out.println(arr[0].length);

        System.out.println(islandNum(arr));
    }

    /**
     * 统计岛屿的数量
     * @param a
     * @return
     */
    private static int islandNum(int[][] a) {
        if (a == null) return 0;

        int islandNum = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if (a[i][j] == 1) {
                    islandNum++;
                    infect(i, j, a.length-1, a[i].length-1, a);
                }
            }
        }
        return islandNum;
    }

    /**
     * 感染连成一片的岛屿
     * @param i
     * @param j
     * @param line 行边界
     * @param column 列边界
     * @param a  二维数组
     */
    private static void infect(int i, int j, int line, int column, int[][] a) {
        if (i<0 || j<0 || i>line || j>column || a[i][j]!=1) return;

        //感染后区别原来的数据
        a[i][j] = 2;
        //往上感染
        infect(i, j-1, a.length-1, a[i].length-1, a);
        //往下感染
        infect(i, j+1, a.length-1, a[i].length-1, a);
        //往左感染
        infect(i-1, j, a.length-1, a[i].length-1, a);
        //往右感染
        infect(i+1, j, a.length-1, a[i].length-1, a);
    }


    private static int[][] createArray() {
        int[][] arr = new int[4][6];
        arr[0][0] = 0;
        arr[0][1] = 0;
        arr[0][2] = 1;
        arr[0][3] = 0;
        arr[0][4] = 1;
        arr[0][5] = 0;

        arr[1][0] = 1;
        arr[1][1] = 1;
        arr[1][2] = 1;
        arr[1][3] = 0;
        arr[1][4] = 1;
        arr[1][5] = 0;

        arr[2][0] = 1;
        arr[2][1] = 0;
        arr[2][2] = 0;
        arr[2][3] = 1;
        arr[2][4] = 0;
        arr[2][5] = 0;

        arr[3][0] = 0;
        arr[3][1] = 0;
        arr[3][2] = 0;
        arr[3][3] = 0;
        arr[3][4] = 0;
        arr[3][5] = 0;
        return arr;
    }

}
